import java.util.Scanner;

/**
 * 购物单
 * 动态规划问题
 * https://blog.csdn.net/chanmufeng/article/details/82955730
 * Created by JiaJia on 2019/6/20 0020.
 */
public class HuaWei016 {
    public static void main(String[] args) {
        /*Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){

        }
        scanner.close();*/
        int[] price={800,400,300,400,500};
        int[] value={1600,2000,1500,1200,1000};
        int[] zhuFu={0,1,1,0,0};
        int N=1000;
        System.out.println(shoppiingList(price,value,zhuFu,N));
    }
    private static int shoppiingList(int[] price,int[] value,int[] zhuFu,int N){
        int size=price.length;
        int[][] dp=new int[size][N+1];
        for (int i = 0; i <=N ; i++) {
            dp[0][i]= price[0]>i ? 0 : value[0];
        }
        for (int i = 1; i <size ; i++) {
            for (int j = 0; j <=N ; j++) {
                if (zhuFu[i]==0){
                    if (price[i]<=j){
                        dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-price[i]]+value[i]);
                    }else {
                        dp[i][j]=dp[i-1][j];
                    }
                }else {
                    if (price[i]+price[zhuFu[i]]<=j){
                        dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-price[i]-price[zhuFu[i]]]+value[i]);
                    }else {
                        dp[i][j]=dp[i-1][j];
                    }
                }
            }
        }
        return dp[size-1][N];
    }
}